#include <iostream>
#include <limits>

// 3.1
class ThreeStacks
{
public:
  ThreeStacks() : idx1(0), idx2(0), idx3(0), idxEnd(0) {}
  void push(int stackNum, int item);
  int pop(int stackNum);
  void printStack(int stackNum) const;
  
private:
  int getStartIndex(int stackNum) const;
  int getEndIndex(int stackNum) const;
  static const int Size = 100;
  int stacks[Size];
  int idx1, idx2, idx3, idxEnd;
};

void ThreeStacks::push(int stackNum, int item)
{
  if (idxEnd >= Size-1)
    return;
  
  int idx = getStartIndex(stackNum);
  
  // shift right
  for (int i = idxEnd; i > idx; --i) {
    stacks[i] = stacks[i-1];
  }
  // insert new item
  stacks[idx] = item;
  
  // update indexes
  switch (stackNum) {
    case 1:
      ++idx2;
    case 2:
      ++idx3;
    case 3:
    default:
      ++idxEnd;
  }  
}

int ThreeStacks::pop(int stackNum)
{
  int res = 0;
  if (idxEnd == 0)
    return res;
  
  int idx = getStartIndex(stackNum);
  res = stacks[idx];
  
  // shift right
  for (int i = idx; i < idxEnd-1; ++i) {
    stacks[i] = stacks[i+1];
  }
  
  // update indexes
  switch (stackNum) {
    case 1:
      --idx2;
    case 2:
      --idx3;
    case 3:
    default:
      --idxEnd;
  }   
}

void ThreeStacks::printStack(int stackNum) const
{
  int from = getStartIndex(stackNum);
  int to = getEndIndex(stackNum);
    
  for(int i = from; i <= to; ++i) {
    std::cout << stacks[i] << " ";
  }
  std::cout << std::endl;
}

int ThreeStacks::getStartIndex(int stackNum) const
{
  int from = 0;
  switch(stackNum) {
    case 1:
      from = 0;
      break;
    case 2:
      from = idx2;
      break;
    case 3:
      from = idx3;
      break;
    default:
      from = 0;
  }
  return from;
}

int ThreeStacks::getEndIndex(int stackNum) const
{
  int to = -1;
  switch(stackNum) {
    case 1:
      to = idx2 - 1;
      break;
    case 2:
      to = idx3 - 1;
      break;
    case 3:
      to = idxEnd - 1;
      break;
    default:
      to = -1;
  }
  return to;
}

// 3.2

struct Node {
  int data;
  Node *pNext;
  
  Node(int d) 
    : data(d), pNext(0) {}
};

class Stack
{
public:
  Stack() : pHead(0), min(std::numeric_limits<int>::max()) {}
  void push(int item);
  int pop();
  int peek();
  bool isEmpty();
  void print();
private:
  Node *pHead;
  int min;
};

void Stack::push(int item)
{
  Node *pNode = new Node(item);
  pNode->pNext = pHead;
  pHead = pNode;
  if(item < min) {
    min = item;
  }
}

int Stack::pop()
{
  int res = 0;
  
  if (0 != pHead) {
      res = pHead->data;
      Node *pTmp = pHead;
      pHead = pHead->pNext;
      delete pTmp;    
  }
  
  return res;
}

int Stack::peek()
{
  int res = 0;
  
  //if (0 != pHead) {
      res = pHead->data;
  //}
  
  return res;
}

bool Stack::isEmpty()
{
  return (pHead == 0);
}

void Stack::print()
{
  Node *pN = pHead;
  while(pN) {
    std::cout << pN->data << " ";
    pN = pN->pNext;
  }
  if (pHead)
    std::cout << "(min: " << min << ")";
  std::cout << std::endl;
}


// 3.6
#include <algorithm>
#include <vector>
#include <vector>
void sortStack(Stack& stack)
{
  std::vector<int> buffer;
  
  // store elements
  while(!stack.isEmpty()) {
    buffer.push_back(stack.pop());
  }    
  
  // selection sort-like algorithm: always insert the minimum
  std::vector<int>::iterator it;
  while(buffer.size() > 0) {
      it = std::min_element(buffer.begin(), buffer.end());
      stack.push(*it);
      buffer.erase(it);
  }
}



int main(int argc, char*argv[])
{
#if 0
// 3.1
  ThreeStacks stacks;
  stacks.push(2, 11);
  stacks.push(1, 1);
  stacks.push(2, 12);
  stacks.push(2, 13);
  stacks.push(3, 31);
  stacks.push(3, 32);
  stacks.push(1, 2);
  stacks.push(3, 33);
  stacks.push(1, 3);
  stacks.push(3, 34);
  stacks.push(2, 14);
  stacks.push(1, 4);
  stacks.push(1, 5);
  stacks.printStack(1);
  stacks.printStack(2);
  stacks.printStack(3);
  stacks.pop(2);
  stacks.pop(1);
  stacks.pop(3);
  stacks.pop(1);
  stacks.printStack(1);
  stacks.printStack(2);
  stacks.printStack(3);
#endif
  
#if 0
// 3.2
  Stack s;
  s.push(1);
  s.push(2);
  s.push(3);
  s.push(4);
  s.push(-4);
  s.push(4);
  s.pop();
  s.print();
#endif

#if 1
// 3.6
Stack s;
  s.push(2);
  s.push(1);
  s.push(3);
  s.push(4);
  s.push(-4);
  s.push(4);
  s.print();
  sortStack(s);
  s.print();
#endif
  
  return 0;
}